package org.xqh.study.leetcode.algorithm.twopointer;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName SubarraysWithKDistinct
 * @Description K 个不同整数的子数组
 * https://leetcode-cn.com/problems/subarrays-with-k-different-integers/
 * @Author xuqianghui
 * @Date 2021/2/9 9:35
 * @Version 1.0
 */
public class SubArraysWithKDistinct {

    public static void main(String[] args) {
//        int[] A = {1, 2, 2, 3, 1, 2, 4, 5};
//        int[] A = {1,2,1,3,4};
        int[] A = {1, 5, 3, 3, 2};

        System.out.println(subArraysWithKDistinct11122(A, 3));
    }


    public static int subArraysWithKDistinct11122(int[] A, int K){
        return maxContainArrayCount(A, K) - maxContainArrayCount(A, K - 1);
    }

    /**
     * 最多包含 K个 整数的 子数组个数
     * @param A
     * @param K
     * @return
     */
    //条件1 <= A.length <= 20000
    //1 <= A[i] <= A.length
    //1 <= K <= A.length
    public static int maxContainArrayCount(int[] A, int K){
        int res = 0;
        int len = A.length;
        if(len < K){
            return len;
        }

        int left  = 0;
        int right = 0;
        int[] freq = new int[len + 1];//频数
        int count = 0;

        while (right < len){
            //移动 右指针
            if(freq[A[right]] == 0){//原频数为0
                count++;
            }
            freq[A[right]]++;
            right ++;

            while (count > K){
                if(freq[A[left]] == 1){
                    count --;
                }
                freq[A[left]]--;
                left++;
            }
            res += right - left;
        }
        return res;
    }

    /**
     * 用map  超时.
     * @param A
     * @param K
     * @return
     */
    public static int subArraysWithKDistinct11(int[] A, int K) {
        int len = A.length;
        if (len < K) {
            return 0;
        }
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>(K);
        for (int i = 0; i < K; i++) {
            map.put(A[i], map.getOrDefault(A[i], 0) + 1);
        }
        res += map.size() == K ? 1 : 0;
        int preAddCount = 0;//前一次循环 添加元素个数
        for (int i = 0; i <= len - K; i++) {
            if (i > 0) {
                //移除上一次循环 加入的元素
                for (int f = 0; f < preAddCount; f++) {
                    //移除
                    int preVal = A[i - 1 + K + f];
                    if (map.get(preVal) == 1) {
                        map.remove(preVal);
                    } else {
                        map.put(preVal, map.get(preVal) - 1);
                    }
                }
                preAddCount = 0;
                int pre = A[i - 1];
                int add = A[i + K - 1];//加上 右侧新增的元素
                if(pre != add){
                    if (map.get(pre) == 1) {
                        map.remove(pre);
                    } else {
                        map.put(pre, map.get(pre) - 1);
                    }

                    map.put(add, map.getOrDefault(add, 0) + 1);
                }
                if(map.size() == K){
                    res ++;
                }
            }
            for (int j = i + K; j < len; j++) {
                int cur = A[j];
                if (map.size() == K && !map.containsKey(cur)) {
                    //长度已经够了
                    break;
                }
                map.put(cur, map.getOrDefault(cur, 0) + 1);
                preAddCount++;//记录 添加了 多少元素
                if (map.size() == K) {
                    res++;
                }
            }
        }
        return res;
    }
}
